#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
    int longestPalindromeSubseq(string s)
    {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 1));
        int maxLength = 0;
        for (int l = 1; l < s.size(); l++)
        {
            if (l == 1)
                for (int x = 0; x < s.size() - l; x++)
                {
                    dp[x][x + l] = s[x] == s[x + l] ? 2 : 1;
                    maxLength = max(maxLength, dp[x][x + l]);
                }
            else
                for (int x = 0; x < s.size() - l; x++)
                {
                    if (s[x] == s[x + l])
                        dp[x][x + l] = dp[x + 1][x + l - 1] + 2;
                    else
                        dp[x][x + l] = max(dp[x + 1][x + l], dp[x][x + l - 1]);
                    maxLength = max(maxLength, dp[x][x + l]);
                    cout << "x:" << x << " y:" << x + l << " dp:" << dp[x][x + l] << endl;
                }
        }
        return maxLength;
    }
};

int main()
{
    cout << "Code516" << endl;
    Solution s;
    cout << s.longestPalindromeSubseq("abcabcabcabc") << endl;
    return 0;
}